package Test.Exam;

import java.util.Scanner;

/**
 * @ClassName problem_1
 * @since: 2024/3/9 09:44
 * @auth: kirito
 * @description:
 **/
public class problem_2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int q = in.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
        }
        while (q-- > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            long min = Min(arr,l,r);
            long max = Max(arr,l,r);
            System.out.println(min + " " + max);
        }
    }

    private static long Max(long[] arr, int l, int r) {
        long max = 0;
        int left=-1;
        int right = -1;
        for (int i = 0; i <= arr.length; i++) {
            if (arr[i] == 0) {
                if (i >= l && i <= r) {
                    max += Math.max(left == -1 ? 0 : arr[left], right == -1 ? 0 : arr[right]);
                }else {
                    if (left == -1 || i <= left) {
                        left = i;
                    }
                    if (right == -1 || i >= right) {
                        right = i;
                    }
                }
            }
        }
        return max;
    }

    private static long Min(long[] arr, int l, int r) {
        long min = 0;
        int left=-1;
        int right = -1;
        for (int i = 0; i <= arr.length; i++) {
            if (arr[i] == 0) {
                if (i >= l && i <= r) {
                    min += Math.min(left == -1 ? 0 : arr[left], right == -1 ? 0 : arr[right]);
                }else {
                    if (left == -1 || i <= left) {
                        left = i;
                    }
                    if (right == -1 || i >= right) {
                        right = i;
                    }
                }
            }
        }
        return min;
    }
}
